Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Прекращение поиска
Прекращение поиска

Очевидно, что требуется более сложная проверка останова. Функция оценки должна применяться только к позициям, которые являются спокойными, т.е. характеризующимися низкой вероятностью того, что в них в ближайшем будущем произойдут резкие изменения в стоимости. Например, в шахматах такие позиции, в которых могут быть сделаны желательные взятия фигур, не являются спокойными для такой функции оценки, в которой учитывается лишь материал. Неспокойные позиции могут быть дополнительно развернуты до тех пор, пока не будут достигнуты спокойные позиции. Подобный дополнительный поиск называется поиском спокойных позиций; иногда он ограничивается тем, что в нем рассматриваются только ходы определенных типов, такие как ходы со взятием фигур, что позволяет быстро устранять все неопределенности в этой позиции.

Задача устранения эффекта горизонта является более сложной. Этот эффект возникает, если программа сталкивается с каким-то ходом противника, который причиняет серьезный ущерб и в конечном итоге является неизбежным. Рассмотрим шахматную позицию, приведенную на рис. 6.7. Черные превосходят белых по количеству материала, но если белые смогут продвинуть свою пешку с седьмой горизонтали на восьмую, то пешка станет ферзем и обеспечит легкую победу белых. Черные могут отсрочить этот итог на 14 полуходов, объявляя шах белым с помощью ладьи, но пешка неизбежно станет ферзем. Одним из недостатков поиска на фиксированную глубину является то, что применяемый при этом алгоритм не позволяет определить, что такие отвлекающие ходы не способны предотвратить ход с превращением пешки в ферзя. В этом случае принято считать, что отвлекающие ходы выводят неизбежный ход с превращением пешки в ферзя "за пределы горизонта поиска" — в то место, где опасный ход невозможно обнаружить.

По мере того как совершенствование аппаратных средств, применяемых для ведения игры в шахматы, приводит к увеличению глубины поиска, становится все более возможным то, что эффект горизонта будет возникать не так часто, поскольку очень длинные последовательности ходов, позволяющие отсрочить выполнение нежелательного хода, возникают крайне редко. Для предотвращения эффекта горизонта без слишком значительного увеличения стоимости поиска оказалось также весьма эффектным использование одинарных расширений. Одинарным расширением называется ход, который "безусловно лучше" по сравнению со всеми другими ходами в данной конкретной позиции. Поиск с одинарным расширением позволяет выйти за обычные пределы глубины поиска без внесения значительных издержек, поскольку в нем коэффициент ветвления равен 1. (Поиск спокойной позиции может рассматриваться как один из вариантов одинарных расширений.) На рис. 6.7 поиск с одинарным расширением позволяет найти выполняемый в конечном итоге ход превращения пешки в ферзя, при условии, что ходы черных с объявлением шаха и ходы белых королем могут быть определены как "безусловно лучшие" по сравнению с другими вариантами.

Рис. 6.7. Проявление эффекта горизонта. Серия шахов черной ладьей приводит к принудительному выводу неизбежного хода белых с превращением пешки в ферзя "за горизонт", в связи с чем эта позиция начинает казаться допускающей выигрыш черных, тогда как фактически она является выигрышной для белых